package com.itheima.linkNode;

import com.itheima.util.ListNode;

public class LeetCode143 {
    /*给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。*/

    public void reorderList(ListNode head) {
        ListNode mid = serchMid(head);
        ListNode head2 = reback(mid);

        while (head2 != mid && head2.next != null){
           ListNode nex = head2.next;
           head2.next = head.next;
           head.next = head2;
           head = head2.next;
           head2 = nex;
        }
    }

    //寻找中节点
    private ListNode serchMid(ListNode head){
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    //反转链表
    private ListNode reback(ListNode head){
        ListNode pre = null;
        ListNode next = head;
        ListNode now = head;

        while (now != null){
            next = next.next;
            now.next = pre;
            pre = now;
            now = next;
        }

        return pre;
    }
}
